package chapter2;

/**
 * @author Hang
 * @date 2022/8/7
 * @project AutumnOffer
 * @description 面试题3 题目二 该题不能修改数组，所以解法一不适用
 **/
public class findRepeatNumber2 {
    public static void main(String[] args) {
        int[] nums = new int[]{2,3,5,4,3,2,6,7};
        System.out.println(findReatNumber2(nums));
        System.out.println(3>>1); //测试
    }
    public static int findReatNumber2(int[] nums){
        if(nums.length<=0) return -1; // 判断数组长度
        int start  = 1, end = nums.length-1; // 定义数组的搜索范围1~7
        while(end >= start){ //
            int mid = ((end - start)>>1) + start; // 中间点
            int count = countRange(nums,start,mid); // 计算区间内的数字个数
            if(end == start){ // 起点终点一致，则判断这个点的数字是否重叠了，是则返回，不是则退出
                if(count > 1) return start;
                else break;
            }
            if(count > (mid - start + 1)) end = mid; // 判断计数的范围与数字范围之间的关系，如果大于则在此区间
            else start = mid + 1; // 否则统计其他区间
        }
        return -1;
    }
    public static int countRange(int[] nums,int start,int end){
        if(nums.length == 0) return 0;
        int count = 0;
        for(int i = 0;i<nums.length;i++){
            if(nums[i]>=start&&nums[i]<=end){
                count++;
            }
        }
        return count;
    }
}
